#include <stdio.h>
#include <stdlib.h>
//#define NULL 0
#define M 100 

typedef struct node{  
    char data;
	int count;
    struct node *lchild;  
    struct node *rchild;
}bitree;
typedef struct stack{
	bitree *elements[M];
	char top;
}seqstack;  //定义一个储存树类型地址的栈，方便遍历的时候追踪到树的地址。

bitree *root;//定义一个树根
seqstack s;//定义栈

void setnull(){//初始化栈
	s.top = 0;
}
void push(bitree *temp){//压栈 
	s.elements[s.top++] = temp;
}
bitree *pop(){//弹栈 
	return s.elements[--s.top];
}
 
int empty()//判断空栈
{
	return s.top == 0;
}
 
bitree *creat(){   /*建立二叉树的递归算法*/
	bitree *t;
	char x;
	scanf("%c",&x);
	if(x!='.'){
		t=(bitree*)malloc(sizeof(bitree));//动态生成结点t,分别给结点t的数据域、左右孩子域  
		t->data=x;           //赋值,给左右孩子域赋值时用到了递归的思想。
		t->lchild=creat();
		t->rchild=creat();
  	}else
  		t = NULL;
  	return t;
}

void preorder(bitree *t){//前序遍历的非递归算法
	bitree *temp = t;//定义一个树节点，用它来遍历ABD..EH...CF.I..G..
	while(temp != NULL || s.top != 0){
		while(temp != NULL){//先遍历左孩子，并输出。ABD..EH...CF.I..G..
			printf("%c",temp->data);
			push(temp);
			temp = temp->lchild;
		}
		if(s.top != 0){//当左孩子遍历完后，取栈顶，找右孩子。此时循环还没有结束，再遍历它的有右孩子，直至孩子全部遍历结束。
			temp = pop();
			temp = temp->rchild;
		}
	}
	printf("\n");
}

int main(){
	bitree *root;//创建根
	setnull();//制空栈
	printf("以先序序列输入树:\n");
	root = creat();//创建二叉树
	printf("前序遍历:\n");
	preorder(root);
	return 0;
}
